﻿/// <summary>
/// https://leetcode-cn.com/problems/4sum/
/// </summary>
public class Solution
{
    private class FourIntListComparer : IEqualityComparer<IList<int>>
    {
        public bool Equals(IList<int>? x, IList<int>? y)
        {
            if (y == null)
                return x == null;
            if (x == null)
                return false;
            return x.SequenceEqual(y);
        }

        public int GetHashCode([System.Diagnostics.CodeAnalysis.DisallowNull] IList<int> obj)
        {
            if (obj.Count == 4)
                return HashCode.Combine(obj[0], obj[1], obj[2], obj[3]);
            else
                throw new NotImplementedException();
        }
    }
    public IList<IList<int>> FourSum(int[] nums, int target)
    {
        var result = new HashSet<IList<int>>(new FourIntListComparer());

        if (nums.Length < 4)
            return new List<IList<int>>();

        Array.Sort(nums);

        for (int base1Index = 0; base1Index < nums.Length - 2; base1Index++)
        {
            for (int base2Index = 0; base2Index < nums.Length; base2Index++)
            {
                var base1Value = nums[base1Index];
                var base2Value = nums[base2Index];

                if (base1Index == base2Index)
                    continue;

                int leftIndex = base1Index + 1, rightIndex = nums.Length - 1;

                for (; leftIndex < rightIndex;)
                {
                    var leftValue = nums[leftIndex];
                    var rightValue = nums[rightIndex];
                    int sum = base1Value + leftValue + rightValue + base2Value;

                    if (sum == target)
                    {
                        if (base2Index == leftIndex || base2Index == rightIndex)
                        {
                            rightIndex--;
                            leftIndex++;
                            continue;
                        }
                        var l = new List<int>() { base1Value, base2Value, leftValue, rightValue };
                        l.Sort();
                        _ = result.Add(l);
                        leftIndex++;
                        rightIndex--;
                    }
                    else if (sum < target)
                        leftIndex++;
                    else // if (sum > target)
                        rightIndex--;
                }
            }
        }

        return result.ToList();
    }
}